
//https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741?tpId=13&tqId=2254224&ru=%2Fpractice%2F57d85990ba5b440ab888fc72b0751bf8&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
// 大数求模 + 快速幂 + 贪心实现，时间复杂度时间复杂度 O(logn)
//

class Solution {
  public:
    long long mod = 998244353;
    long long Pow(long long b, long long n) { //快速幂
        if (n == 0){
            return  1;
        }
        else if (n&0x01) {
            return Pow(b, n-1)*b %mod;
        }
        else {
            long long tmp = Pow(b, n>>1);
            tmp = tmp % mod;
            return tmp*tmp%mod;
        }
    }

    long long cutRope(long long number) {
        if (number <= 3) //不超过3直接计算
            return number - 1;
        if (number % 3 == 0) //能整除3
            return Pow(3, number / 3);
        else if (number % 3 == 1) //最后剩余1
            return Pow(3, number / 3 - 1)* 4 %mod; //4*3^{n-1}
        else //最后剩余2
            return Pow(3, number / 3)* 2 %mod; //2*3^n
    }
};
